The present invention pertains to the field of computer networks. More specifically, the present invention pertains to the field of distributed architectures for virtual reality environment systems.
Development in software technology has allowed computers to perform a wide variety of useful operations. Depending on the software which is installed within their particular memory storage devices, computers can be used for many purposes. For example, they can be used to manage numerous financial transactions of a bank, control the fabrication of items ranging from automobiles to integrated circuit chips, store addresses and telephone numbers of acquaintances, analyze scientific and engineering data, produce and edit documents along with transmitting and receiving data.
The functionality and usefulness of a computer system is further enhanced by the promulgation of the Internet. The Internet is a worldwide collection of computer networks and gateways that generally use the TCP/IP suite of protocols to communicate with one another. Millions of people use the Internet for communication and entertainment. The Internet allows easy access to media and data from a variety of sources, and is capable of delivering this information to the users wherever they may be. Further, the Internet can support a high degree of interaction, allowing the users to interact with other users and to carry out useful work with others even when they are geographically remote.
The promulgation of the Internet has also spawned interests in developing virtual reality systems that allow many users to participate and interact with each other in a shared three-dimensional (3D) virtual environment. In response to such interests, a shared, multi-user virtual environment system targeted at personal computer platforms with low-speed connection to the Internet has been developed by the Sony Corporation. The purpose of Sony""s virtual environment system (known as Community Place or CP) is to provide an efficient way for people to participate and interact in a 3D virtual world while being geographically dispersed.
FIG. 1 is a block diagram illustrating the architecture of Sony""s Community Place (CP) system 100. The CP architecture adopts a client-server model. It is composed of the following components: a CP server 110 that consists of a database of objects existing in the 3D virtual world, and a number of CP clients 120a-120c connected to the CP server 110 for accessing contents of the database. The CP clients 120a-120c each includes a CP browser which can handle VRML files and web URLs for displaying the 3D virtual world, and for allowing users to navigate through the virtual world and to interact with other users and objects in the world.
Clients 120a-120c are connected to CP server 110 via the Internet 130. Communication between the clients 120a-120c and the CP server 110 is accomplished by using the Virtual Society Client Protocol (VSCP). This protocol has been designed to provide efficient virtual scene update information and support for script specific messages. As Community Place is designed for low-bandwidth Internet connections, the VSCP messages are made as compact as possible.
Each client 120a-120c is represented by an xe2x80x9centityxe2x80x9d within the virtual world. The CP server 110 is mainly responsible for maintaining consistency between the clients 120a-120c, tracking position of entities, and forwarding messages coming from one client to the others. The position-tracking function of the CP server is accomplished by using a User Application Manager (UAM).
To reduce the computation load of the server 110, the Community Place architecture employs the notion of spatial area of interest (AOI). The Area of Interest (also called aura) represents a zone around an entity. The entity may interact with other entities located inside this aura. The benefit of this approach is that it decreases the number of messages to be sent in case of a modification. Indeed, only entities inside the aura of a particular entity receive update information concerning that particular entity. Thus, another function of the server 110 is to determine, using the aura manager, the set of entities to be notified of a modification in the virtual world. The aura manager also determines when a collision between two auras occur. As background, a more detailed description of the Community Place architecture can be found in a reference by Lea et al., entitled xe2x80x9cCommunity Place: Architecture and Performance,xe2x80x9d VRML""97xe2x80x942nd Symposium on the Virtual Reality Modeling Language, February 1997.
The CP system 100 is tremendously successful in providing access to a shared virtual environment to hundreds of clients simultaneously. However, current computer technology limits the number of clients that can be connected to the CP server 110. For instance, it has been shown that a CP server implemented on a Sun Sparc Ultra-Server model-170 can only handle approximately five hundred simultaneous connections. In addition, because clients may be geographically very far from each other, a single server is not an efficient solution as the low-bandwidth connection between a client 120a-120c and the CP server 110 can cause substantial latency and delay. As the number of clients increases, the number of messages on the network is also a concern. Further, the virtual worlds and their applications are becoming so complex that a single server can barely manage the necessary computations. Finally, a single server architecture is not fool-proof as a failure of this server would have dramatic consequences on the shared virtual world.
Beside Community Place, other distributed shared virtual environment systems have also been proposed. For example, NPSNET, developed by the U.S. Navy and described in a reference by Macedonia et al., entitled xe2x80x9cExploiting Reality With Multicast Groups,xe2x80x9d IEEE Computer graphics and Applications, Vol. 15, pp. 38-45, is a large-scale virtual environment and is intended to support military simulations that include tens of thousands of users. In NPSNET, the virtual world is partitioned in hexagons and a multicast group is associated to each of these hexagon. The NPSNET, however, is most efficient when the distribution of entities within the virtual world is homogenous. The NPSNET architecture, however, loses significant amount of efficiency when a large number of entities are located in the same hexagon.
Another well-known distributed virtual environment system is the DIVE system developed at the Swedish Institute of Computer Science, and described in a reference by Frecon et al., entitled xe2x80x9cDIVE: A Scalable Network Architecture for Distributed Virtual Environments,xe2x80x9d Distributed System Engineering, Vol. 5, pp. 91-100. To remedy problems with network congestion and traffic overhead, the DIVE system provides a mechanism for dividing the virtual world into sub-hierarchies that are only replicated and used in between the applications that are actually interested in them. Although only a portion of the virtual world database is replicated at each process, each host must nonetheless maintain the entire database. Thus, the DIVE architecture may not be suitable for a very large scale virtual environment.
Therefore, there exists a need for a more reliable architecture that is capable of handling a large scale virtual environment having a very large number of users. What is also needed is an architecture that is capable of handling large scale virtual environment without sacrificing complexity in the virtual worlds and application designs. What is yet further needed is an architecture for distributed virtual environment systems that is not based on geographical partitioning of the virtual environment.
A computer implemented process and system are described for distributing computation processes among a network of servers within a large scale shared virtual environment system. According to the present invention, entities within the virtual environment are gathered in groups based on their interactions. Entities that can potentially interact with each other are gathered in one group. In one embodiment of the present invention, the Area of Interest (or aura) of each entity is used as a means for identifying possible interactions between entities.
According to the present invention, the groups are mapped onto the available servers of the network. Once a group is mapped to a server, the server will become responsible for managing interaction between the entities of the group. In addition, a server has to perform collision detection and other computation intensive operations for the group that it manages. In addition, the server is responsible for replicating non-local entities of the interaction group it manages so that every user can see all the entities within his group. Thus, by mapping the groups to the server, computation load can be evenly distributed.
Embodiments of the present invention include the above and further include a computer implemented method of sharing computation load among the network of servers comprising the steps of: providing a shared multi-user virtual environment including a number of entities; and dynamically assigning each of the entities to a server of the network. According to the present embodiment, the step of dynamically assigning further includes the steps of: (a) collecting spatial information of the of entities from the servers; (b) forming a number of groups by grouping the plurality of entities based on the spatial information; (c) distributing computational load among the network of servers by mapping each interaction group to one of the network of servers. In the present invention, the steps (a) to (c) are repeated periodically such that consistency is maintained between the constituency of the groups and changes in the virtual environment.